Integrated circuit technology has reduced the cost of electronic systems to the point where almost any member of the public can now own a computer which has capabilities which could have been found only in the largest industrial and military laboratories a short twenty years ago. The trend towards reduced size, reduced cost and the placement of more and more components on a single chip has continued unabated. VLSI (Very Large Scale Integration) technology is the current terminology for the results of this trend. The present invention is in the VLSI technology.
One of the major problems in the VLSI technology is the following: given the logical design of a circuit, how can the components and/or circuit modules be best positioned to minimize the area (or length) of the interconnections between the modules. The primary purpose of this minimization is to enable the placement of as many instances of the chip as possible on a single semiconductor wafer, thereby reducing fabrication costs. Another purpose is to reduce the path length and delay and thus increase the speed of operation. One variant of this problem is the layout of a circuit made up of standard cells or "polycells" which can be laid out in rows of identical or near identical circuitry. Common signals such as power, ground and clocks are then routed through busses within the rows of cells. Terminals at the top and bottom of each cell are used to connect the cells to each other by conductive paths in the channels between the rows of cells.
One approach to the placement of circuit modules on an integrated circuit substrate was taken in U.S. Pat. No. 3,617,714, granted Nov. 2, 1971 and assigned to applicants' assignee. In this patent, the modules and their interconnections are treated as the vertices and edges, respectively, of a graph. Optimum, or near optimum, partition of the vertices of the graph are obtained by creating an arbitrary partition and then iteratively exchanging pairs or groups of vertices to find a better partition, i.e., a partition with fewer interpartition edges. Once partitioned, each subset is itself partitioned, and so forth, until the relative positions of all of the circuit modules are closely circumscribed. The specific details of this approach and its mathematical justification can be found in the above-mentioned patent 3,617,714.
The technique of the above-noted Kernighan and Lin patent can be advantageously used to identify clusters of circuit components or polycells which can advantageously be placed close to each other. Unfortunately, however, other constraints on the placement of circuit modules must also be observed in any real placement of modules on integrated circuit chips. One such major constraint is the placement of the other integrated circuit modules, i.e., connectivity constraints outside of the placement subarea. Obviously, a component layout which does not take such external module placement constraints into account will be subject to significant placement errors which either must be corrected or else suffer the resulting increase in interconnection lengths. Indeed, any scheme which attempts to modify an optimized placement after the placement is selected so as to account for constraints like the terminals of external module placement runs the risk of losing any advantage thereby gained.